1. Field of the Invention
This invention relates generally to interleaving techniques associated with correction of error bursts in ADSL/VDSL digital communication systems, and more particularly to a method of efficiently generating addresses for Forney's modular periodic interleavers to minimize memory requirements.
2. Description of the Prior Art
Interleaving techniques have often been used in conjunction with error correction codes to correct error bursts and to improve the reliability of ADSL/VDSL communication systems. A typical interleaving scheme 10 is shown in FIG. 1 that includes an encoder 12 for encoding an incoming stream of data and an interleaver 14 that interleaves the encoded signal such that the error burst in a channel 16 is spread over multiple code words as a result of the interleaving scheme 10. The encoding and interleaving of data occur as part of the data transmission process of a transmitter. The encoded interleaved signal is then received by a receiver that includes a de-interleaver 18 that unscrambles the interleaving, and a decoder 20 that decodes the encoded signal. More specifically, the interleaver 14 permits the ordering of the sequence of symbols in a deterministic manner, while the de-interleaver applies an inverse permutation to restore the sequence to it original ordering.
A row-column block interleaver 100 is shown in FIG. 2 that is useful to describe the type of permutation implemented by an interleaver. The input symbol stream is divided into blocks of data having a designated Length 102. Also defined is an interleaving Depth 104. Data is written into a memory 106 that is divided into a number of rows of Length 102 equal to a designated number of symbols per block and a number of columns equal to a desired interleaving Depth 104. Data is read into the interleaver memory 106 in a column-by-column fashion, and is read out of the interleaver memory 106 in a row-by-row fashion. An amount of memory equal to Length*Depth is then used for a single block of data. Two such blocks are typically used to permit data to be read from one memory block while the other memory block is being written into. Inverse permutation is accomplished by writing into the de-interleaver in a row-by-row fashion and reading out of the de-interleaver in a column-by-column fashion. Those skilled in the art will readily appreciate the total amount of memory necessary to implement such a system is typically 4*Length*Depth; and the total latency through the interleaver and de-interleaver is 2*Length*Depth.
FIG. 3 depicts one embodiment of a double buffered memory 200 that is suitable for implementing row-column block interleaving such as described herein above. The interleaving process is straightforward as the lower numbers in memory A 202 represent time slots for writing; while the upper numbers in memory B 204 represent time slots for reading. A relatively large period equal to Length*Depth is also a concern when using a row-column block interleaving scheme. A row-column block interleaver can be specified completely by a sequence of periodic delays f(0), f(1), . . . , such as, for example, (24,26,28, . . . , 36,38,17,19,21, . . . , 29,31,10,12,14, . . . , 22,24, . . . ) in FIG. 3. These delays are non-negative (causal). An interleaver is periodic if the sequence of delays f(0), f(1), . . . , are periodic. All practical interleavers are periodic. Periodic interleavers were first introduced by Ramsey and Forney around 1970. See, for example, J. L. Ramsey, “Realization of Optimum Interleavers”, IEEE Information Theory, Vol. IT-16, Number 3, May 1970, pp. 338–345; and G. D. Forney, “Burst-Correcting Codes for the Classic Bursty Channel,” IEEE Trans. Communication Technology, Vol. COM-19, Oct. 1971, pp. 772–781.
U.S. Pat. No. 5,764,649, entitled “Efficient Address Generation For Convolutional Interleaving Using a Minimal Amount Of Memory,” issued Jun. 9, 1998 to Po Tong, describes a convolutional interleaving process utilizing an addressing scheme which enables the amount of memory used to be reduced. The described interleaving process uses a plurality of delay related arrays which cooperate with a designated block length to define the delay associated with each symbol in a given block, as well as an initial value array, a lower limit array, and an upper limit array. The initial value, lower limit and upper limit arrays are computed during start-up and used to generate a convolutional interleaving addressing scheme.
In view of the foregoing, it would be highly desirable and advantageous to provide an improved addressing scheme that further reduces the amount of computations to set up the interleavers during start-up.